/*
 * @(#)$Id: codetemplate_xbird.xml 943 2006-09-13 07:03:37Z yui $
 * 
 * Copyright 2006-2008 Makoto YUI
 * 
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
 * in compliance with the License. You may obtain a copy of the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software distributed under the License
 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
 * or implied. See the License for the specific language governing permissions and limitations under
 * the License.
 * 
 * Contributors: Makoto YUI - initial implementation
 */
package jacky.lanlan.song.util.codec;

import jacky.lanlan.song.io.bit.BitUtils;
import jacky.lanlan.song.io.stream.BitInputStream;
import jacky.lanlan.song.lang.BitStringUtils;

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Arrays;

/**
 * 
 * <DIV lang="en"></DIV> <DIV lang="ja"></DIV>
 * 
 * @author Makoto YUI (yuin405+xbird@gmail.com)
 * @link http://en.wikipedia.org/wiki/Elias_gamma_coding
 * @link http://en.wikipedia.org/wiki/Elias_delta_coding
 * @link http://en.wikipedia.org/wiki/Golomb_coding
 * @link http://urchin.earth.li/~twic/Golomb-Rice_Coding.html
 * @link http://www.cs.otago.ac.nz/cosc463/2005/compress.htm
 */
public final class BitwiseCodec implements Cloneable {

	/** optiomal for range 1-1000 */
	public static final int LOG2M4 = 2;

	private byte[] codes;

	private int pos = 0;

	private int pendingBits = 0;

	private int curByte = 0;

	public BitwiseCodec(int bytes) {
		codes = new byte[bytes];
	}

	private BitwiseCodec(BitwiseCodec toClone) {
		byte[] origCodes = toClone.codes;
		this.codes = Arrays.copyOf(origCodes, origCodes.length);
		this.pos = toClone.pos;
		this.pendingBits = toClone.pendingBits;
		this.curByte = toClone.curByte;
	}

	public void reset() {
		pos = 0;
		pendingBits = curByte = 0;
		Arrays.fill(codes, (byte) 0);
	}

	public int putGamma(int val) {
		if (val == 1) {
			putBit(1);
			return 1;
		}
		int logbits = 2;
		for (; logbits < 32; logbits++) {
			if (val < (1 << logbits)) {
				break;
			}
		}
		final int ret = (logbits << 1) - 1;
		if (logbits < 16) {// optimization
			putBits(val, ret);
		}
		else {
			putBits(0, logbits - 1);
			putBits(val, logbits);
		}
		return ret;
	}

	public int putDelta(int val) {
		assert (val > 0) : val;
		if (val == 1) {
			putBit(1);
			return 1;
		}
		int logbits = 2;
		for (; logbits < 32; logbits++) {
			if (val < (1 << logbits)) {
				break;
			}
		}
		int ret = putGamma(logbits);
		int databits = logbits - 1;
		putBits(val, databits);
		ret += databits;
		return ret;
	}

	public int putGolomb4(final int val) {
		return putGolomb(val, 4, LOG2M4);
	}

	public int putGolomb(final int val, final int divm) {
		return putGolomb(val, divm, BitUtils.mostSignificantBit(divm));
	}

	public int putGolomb(final int val, final int m, final int logm) {
		int quotient = val / m;
		for (int i = 0; i < quotient; i++) {
			putBit(0);
		}
		putBit(1);
		int remainder = val % m;
		int mask = 1 << (logm - 1);
		for (int i = logm; i >= 0; i--) {
			putBit(remainder & mask);
			mask >>>= 1;
		}
		int bits = quotient + 1 + logm;
		return bits;
	}

	public long putGolombL(final long val, final long m, final int logm) {
		long quotient = val / m;
		if (quotient > 0x7fffffffL) {
			for (long i = 0; i < quotient; i++) {
				putBit(0);
			}
		}
		else if (quotient > 0) {
			final int qi = (int) quotient;
			for (int i = 0; i < qi; i++) {
				putBit(0);
			}
		}
		putBit(1);
		long remainder = val % m;
		long mask = 1 << (logm - 1);
		for (int i = logm; i >= 0; i--) {
			final long b = remainder & mask;
			putBit(b == 0L ? 0 : 1);
			mask >>>= 1;
		}
		long bits = quotient + 1 + logm;
		return bits;
	}

	public void putBits(int val, int num) {
		for (int i = num - 1; i >= 0; i--) {
			putBit((val >> i) & 0x01);
		}
	}

	public void putBit(int b) {
		curByte = (curByte << 1) | b;
		pendingBits++;

		if (pendingBits == 8) {
			if (pos >= codes.length) {
				expand();
			}
			codes[pos++] = (byte) (curByte & 0xff);
			curByte = 0;
			pendingBits = 0;
		}
	}

	public void allocateNewByte(byte b) {
		padVector();
		if (pos >= codes.length) {
			expand();
		}
		codes[pos++] = b;
		curByte = 0;
		pendingBits = 0;
	}

	private void expand() {
		byte[] oldVector = codes;
		int oldSize = oldVector.length;
		int newSize = (int) (oldSize * 1.75);
		byte[] newVector = new byte[newSize];
		System.arraycopy(oldVector, 0, newVector, 0, oldSize);
		this.codes = newVector;
	}

	private void padVector() {
		if (pendingBits == 0) { return; }
		if (pos >= codes.length) {
			expand();
		}
		codes[pos++] = (byte) ((curByte << (8 - pendingBits)) & 0xff);
	}

	public byte[] getBytes() {
		padVector();
		final byte[] copy = new byte[pos];
		System.arraycopy(codes, 0, copy, 0, pos);
		return copy;
	}

	public void writeTo(final OutputStream out, final boolean clear) throws IOException {
		padVector();
		writeInt(pos, out);
		out.write(codes, 0, pos);
		if (clear) {
			reset();
		}
	}

	private static void writeInt(final int v, final OutputStream out) throws IOException {
		out.write((v >>> 24) & 0xFF);
		out.write((v >>> 16) & 0xFF);
		out.write((v >>> 8) & 0xFF);
		out.write((v >>> 0) & 0xFF);
	}

	public void getBytes_clear(final OutputStream out) throws IOException {
		padVector();
		out.write(codes, 0, pos);
		reset();
	}

	@Override
	public String toString() {
		return BitStringUtils.toBitString(getBytes());
	}

	@Override
	public BitwiseCodec clone() {
		BitwiseCodec cloned = new BitwiseCodec(this);
		return cloned;
	}

	public static long requiredBytesGolomb(final long val, final long divm, final int logm) {
		long quotient = val / divm;
		long bits = quotient + 1 + logm;
		return bits;
	}

	public static long decodeGolombL(final byte[] b, final long m, final int logm) {
		long unary = 0;
		final int blen = b.length;
		for (int i = 0; i < blen; i++) {
			int msb = BitUtils.mostSignificantBit(b[i]);
			if (msb == 7) { // 1000
				break;
			}
			else if (msb == -1) {// 0000
				unary += 8;
			}
			else {
				unary += (7 - msb);
				break;
			}
		}
		/* Get the first q bits (we may need (q+1) actually) */
		long remainder = BitUtils.getLongBits(b, unary + 1, logm);

		long ret = unary * m + remainder;
		return ret;
	}

	public static long decodeGolombL(final InputStream in, final long m, final int logm) throws IOException {
		final BitInputStream bis = new BitInputStream(in);

		long unary = 0;
		while (!bis.readBit()) {// loop until '1' is found
			unary++;
		}

		/* Get the first q bits (we may need (q+1) actually) */
		long remainder = BitUtils.getLongBits(bis, logm);

		long ret = unary * m + remainder;
		return ret;
	}

	/*
	 * public static void main(String[] args) { BitwiseCodec codes = new BitwiseCodec(4);
	 * System.out.println("--------- delta coding ---------"); codes.putDelta(1);
	 * System.out.println("1 = " + StringUtils.toBitString(codes.getBytes())); codes.reset();
	 * codes.putDelta(2); System.out.println("2 = " + StringUtils.toBitString(codes.getBytes()));
	 * codes.reset(); codes.putDelta(3); System.out.println("3 = " +
	 * StringUtils.toBitString(codes.getBytes())); codes.reset(); codes.putDelta(4);
	 * System.out.println("4 = " + StringUtils.toBitString(codes.getBytes())); codes.reset();
	 * codes.putDelta(5); System.out.println("5 = " + StringUtils.toBitString(codes.getBytes()));
	 * codes.reset(); codes.putDelta(6); System.out.println("6 = " +
	 * StringUtils.toBitString(codes.getBytes())); codes.reset(); codes.putDelta(7);
	 * System.out.println("7 = " + StringUtils.toBitString(codes.getBytes())); codes.reset();
	 * codes.putDelta(8); System.out.println("8 = " + StringUtils.toBitString(codes.getBytes()));
	 * codes.reset(); codes.putDelta(9); System.out.println("9 = " +
	 * StringUtils.toBitString(codes.getBytes())); codes.reset(); codes.putDelta(10);
	 * System.out.println("10 = " + StringUtils.toBitString(codes.getBytes())); codes.reset();
	 * codes.putDelta(11); System.out.println("11 = " + StringUtils.toBitString(codes.getBytes()));
	 * codes.reset(); codes.putDelta(12); System.out.println("12 = " +
	 * StringUtils.toBitString(codes.getBytes())); codes.reset(); codes.putDelta(13);
	 * System.out.println("13 = " + StringUtils.toBitString(codes.getBytes())); codes.reset();
	 * codes.putDelta(14); System.out.println("14 = " + StringUtils.toBitString(codes.getBytes()));
	 * codes.reset(); codes.putDelta(15); System.out.println("15 = " +
	 * StringUtils.toBitString(codes.getBytes())); codes.reset(); codes.putDelta(16);
	 * System.out.println("16 = " + StringUtils.toBitString(codes.getBytes())); codes.reset();
	 * codes.putDelta(17); System.out.println("17 = " + StringUtils.toBitString(codes.getBytes()));
	 * codes.reset(); codes.putDelta(Integer.MAX_VALUE); System.out.println(Integer.MAX_VALUE + " = "
	 * + StringUtils.toBitString(codes.getBytes()));
	 * 
	 * System.out.println("--------- Golomb-Rice coding ---------"); codes.reset(); final int logm =
	 * BitUtils.mostSignificantBit(4L); for(int i = 0; i < 18; i++) { codes.putGolombL(i, 4L, logm);
	 * final byte[] bi = codes.getBytes(); System.out.print(Integer.toString(i) + " = " +
	 * StringUtils.toBitString(bi)); System.out.print(", decoded = " + decodeGolombL(bi, 4L, logm));
	 * FastByteArrayInputStream is = new FastByteArrayInputStream(bi); try {
	 * System.out.println(", stream-decoded = " + decodeGolombL(is, 4L, logm)); } catch (IOException
	 * e) { throw new IllegalStateException(e); } codes.reset(); } }
	 */
}
